package seqlist.LeetCode;
//203. 移除链表元素
//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

/**
 * 思路一：最普通的方法，找前驱，和 特殊处理头节点
 */


/*

public class Num_203_removeElements {
    public ListNode removeElements(ListNode head, int val) {
        //保证头节点不是待删除的数
        //1.必须先保证heal不是空指针，才能继续访问里面的val值
        while(head != null && head.val == val){
            //1.0
//            ListNode node = head;
//            head = node.next;
//            node.next = null;
            //其实题目里给的链表，不需要考虑回收、释放的问题，可以直接支这样写
            //2.0
            head = head.next;
        }
        //走到这就保证了头节点不再是待删除的数
        //先判空
        if(head == null){
            return null;
        }else{
            //到这里说明头节点不是待删除的节点
            //开始找前驱
            ListNode prve = head;
            while(prve.next != null ){
                if( prve.next.val == val ) {
                    prve.next = prve.next.next;
                }else{
                    //只有不等于val值，才能移动前驱
                    prve = prve.next;
                }

            }
        }
        return head;
    }
}

 */

/**
 * 思路二：递归写法。题目值给了我们头节点，那我们就只判断头节点是否是需要删除的节点，
 * 剩下的节点交给子方法去处理并把结果返回。
  */

/*

public class Num_203_removeElements {

    public ListNode removeElements(ListNode head, int val) {


        //1.什么情况下不需要拆分了？：终止条件
        if( head == null ){
            return null;
        }else{
            //要用head.next来接收子函数的返回值
            head.next =  removeElements(head.next, val);
            if(head.val == val){//跳过
                head = head.next;
            }
        }
        return head;

    }
}

 */

/**
 * 思路三： 创建一个虚拟头节点来删除。
 * 之前删除老是需要考虑特殊的头节点问题，之前就给头节点创出来一个虚拟节点
 */

public class Num_203_removeElements {

    public ListNode removeElements(ListNode head, int val) {
        //判断是否为空
        if(head == null){
            return head;
        }
        //创建出一个虚拟头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;//连接

        ListNode prve = dummyHead;//前驱
        while(prve.next != null){
            if(prve.next.val == val){
                prve.next = prve.next.next;
            }else{
                prve = prve.next;
            }
        }

        return dummyHead.next;
    }

}






class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
